package com.leetcode.www;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Creared with IntelliJ IDEA.
 * Description:n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
 * 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
 * 第一个整数是 0
 * 一个整数在序列中出现 不超过一次
 * 每对 相邻 整数的二进制表示 恰好一位不同 ，且
 * 第一个 和 最后一个 整数的二进制表示 恰好一位不同
 * 给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/gray-code
 *
 * User:yxd
 * Date:2022-01-08
 * Time:17:41
 */
public class Everyday89 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        List<Integer> a = new ArrayList<>();
        a.add(0);//放入第一个数0
        for (int i = 1; i <= n; i++) {
            int x = a.size();
            //反转序列 然后 给后，面的 每一位二级制数追加1
            for (int j = x - 1; j >= 0 ; j--) {
                //|相或有1则为1
                a.add(a.get(j)|1 << (i - 1));//1<<(i -1)就是2的（i-1）次方
            }
        }
        System.out.println(a);
    }
}
